package cn.good.yan.sf.t6.priority;

/**
 * 6 合并链表  （小顶堆）
 *
 * @author shengren.yan
 * @create 2024-07-06
 */
public class MergeNode {

    public int value;
    public MergeNode next;

    public MergeNode() {
    }

    public MergeNode(int value, MergeNode next) {
        this.value = value;
        this.next = next;
    }

    public void loop() {
        for (MergeNode i = this; i != null; i = i.next) {
            System.out.println(i.value);
        }
    }

    // 合并多个链表
    public MergeNode mergeAll(MergeNode[] arr) {
        if (arr.length == 0) {
            return null;
        }

        PriorityQueue5 queue = new PriorityQueue5(arr.length);
        for (int i = 0; i < arr.length; i++) {
            queue.offer(arr[i]);
        }
        MergeNode head = new MergeNode(-1, null);
        MergeNode p = head;
        while (!queue.isEmpty()) {
            MergeNode n = queue.pool();
            p.next = n;
            p = n;
            if (n.next != null) {
                queue.offer(n.next);
            }
        }
        return head.next;
    }

    public static void main(String[] args) {
        MergeNode a3 = new MergeNode(5, null);
        MergeNode a2 = new MergeNode(3, a3);
        MergeNode a1 = new MergeNode(1, a2);

        MergeNode b5 = new MergeNode(8, null);
        MergeNode b4 = new MergeNode(7, b5);
        MergeNode b3 = new MergeNode(4, b4);
        MergeNode b2 = new MergeNode(2, b3);
        MergeNode b1 = new MergeNode(2, b2);

        System.out.println("------------");
        MergeNode c3 = new MergeNode(10, null);
        MergeNode c2 = new MergeNode(9, c3);
        MergeNode c1 = new MergeNode(1, c2);

        MergeNode d2 = new MergeNode(14, null);
        MergeNode d1 = new MergeNode(12, d2);
        MergeNode[] arr = {
                a1, b1, c1, d1
        };
        MergeNode r3 = a1.mergeAll(arr);
        r3.loop();
    }

}
